{ "cells": [ { "cell_type": "markdown", "metadata": { "collapsed": true, "pycharm": { "name": "#%% md\n" } }, "source": [ "# The chilling adventures of Sabrina\n", "## Problem definition\n", "Spellman´s Ltd is a company that manufactures chilling soft drinks. They want to manufacture two types of drinks A, and B. Both beverages use a semi-elaborate C, another expensive ingredient D and other ingredients that are not relevant for production planning. Sabrina is a young student of engineering and management doing an internship at Spellman´s. She needs to formulate a Continuous Linear Program to configure the optimal daily production plan for the company.\n", "\n", "The selling price of drink A is 3€/liter and the selling price of drink B is 2€/liter.\n", "\n", "1 liter of drink A uses 3 grams of ingredient D. A liter of drink B uses 1 gram of ingredient D. There are only 3 grams of ingredient D available per day.\n", "\n", "The factory only has one mixer to elaborate both drink types and the semi-elaborate. It takes 1 hour to process a liter of drink A, 1 hour to process 1 liter of drink B, and 1 hour to process 1cl of semi-elaborate C. The mixer is available 6 hours per day.\n", "\n", "Drink A uses 2cl of semi-elaborate C and drink B uses 1cl of semi-elaborate C. The company has 3cl of semi-elaborate C plus the amount they decide to produce available per day.\n", "\n", "**1.** Write a Continuous Linear Problem to help Sabrina design the optimal production plan that maximises revenues for the company.\n", "\n", "**Decision variables**:\n", "- $x_A$: Production of drink A in liters\n", "- $x_B$: Production of drink B in liters\n", "- $x_C$: Production of semi-elaborate C in centiliters\n", "\n", "$x_A, x_C, x_B \\in \\mathbb{R}$\n", "\n", "**Objective function**\n", "\n", "$\\max z = 3*x_A + 2*x_B$\n", "\n", "z is the profit in euros. \n", "\n", "**Constraints**\n", "s.t.\n", "\n", "- Availability of ingredient D in grams:\n", "\n", "$3*x_A + x_B \\leq 3$\n", "\n", "- Availability of mixer in hours: \n", "\n", "$x_A + x_B + x_C \\leq 6$\n", "\n", "- Availability of semi-elaborate C in centiliters: \n", "\n", "$2*x_A + x_B -x_C \\leq 3$\n", "\n", "- Logical constraint\n", "\n", "$ x_A, x_C, x_B \\geq 0$\n", "\n", "**2.** Write the dual problem\n", "The dual is: \n", "\n", "$\\min z = 3*u_1 + 6*u_2 + 3*u_3$\n", "\n", "s.t.\n", "\n", "$3*u_1 + u_2 + 2*u_3 \\geq 3$\n", "\n", "$u_1 + u_2 + u_3 \\geq 2$\n", "\n", "$u_2 - u_3 \\geq 0$\n", "\n", "**3.** Given the following solution:\n", "\n", "- 0 Liters of drink A\n", "- 3 Liters of drink B\n", "- 3 cl of semi-elaborate C\n", "\n", "Verify the solution. Is the solution feasible? What are the values of the slack variables?\n", "\n", "We plug in the values of the solution in our constraints: \n", "- Availability of ingredient D in grams:\n", "\n", "$3*x_A + x_B \\leq 3$\n", "\n", "$3*0 + 3 \\leq 3$\n", "\n", "$3 + s_1 = 3$\n", "\n", "$s_1 = 0$\n", "\n", "- Availability of mixer in hours: \n", "\n", "$x_A + x_B + x_C \\leq 6$\n", "\n", "$0 + 3 + 3 \\leq 6$\n", "\n", "$6 + s_2 = 6$\n", "\n", "$s_2 = 0$\n", "\n", "- Availability of semi-elaborate C in centiliters: \n", "\n", "$2*x_A + x_B -x_C \\leq 3$\n", "\n", "$2*0 + 3 - 3 \\leq 3$\n", "\n", "$0 + s_3 = 3$\n", "\n", "$s_3 = 3$\n", "\n", "\n", "- Logical constraint\n", "\n", "$ s_1, s_2, s_3 \\geq 0$\n", "\n", "The solution is feasible because it meets all constraints and slack variables are non-negative.\n", "\n", "**4.** Use complementary slackness to find the dual solution corresponding to this vertex. Is the dual solution \n", "feasible? Is the solution optimal? Motivate your response.\n", "\n", "By complementary slackness, since $s_3=3$, we know that $u_3 = 0$, and also, since $x_C$ is greater than zero, we know \n", " that the third constraint of the dual is binding. By plugging this information into the third constraint we obtain: \n", "\n", "$u_2 - u_3 = 0$\n", "\n", "$u_2 = 0$\n", "\n", "We can plug this value into the second constraint of the dual, which is also binding since $x_B$ is non-zero, to obtain: \n", "\n", "$u_1 + u_2 + u_3 = 2$\n", "\n", "$u_1 = 2$\n", "\n", "All values are non-negative, so the solution is feasible and since both primal and dual are feasible, the solution is \n", "optimal.\n", "\n", "Gurobi provides the following solution:\n", "\n", "Optimal\n", "\n", "Total profit is 6.00 €\n", "\n", "The following table shows the decision variables: \n", "\n", "| j | Variables | Solution (GRB) | Reduced cost (GRB) | Objective Coefficient (GRB) | Objective Lower bound (GRB) | Objective Upper bound (GRB) |\n", "|:---|:------------|-----------------:|---------------------:|------------------------------:|------------------------------:|------------------------------:|\n", "| A | units_A | 0 | -3 | 3 | -inf | 6 |\n", "| B | units_B | 3 | 0 | 2 | 1 | inf |\n", "| C | units_C | 3 | 0 | 0 | -0 | 1.5 |\n", "\n", "The following table shows the constraints: \n", "\n", "| j | Constraint | Slack | Shadow Price | Right Hand Side | Min RHS | Max RHS |\n", "|---:|:-------------------------------|--------:|---------------:|------------------:|----------:|----------:|\n", "| 0 | Availability_of_ingredient_A | 0 | 2 | 3 | 0 | 4.5 |\n", "| 1 | Availability_of_mixer_hours | 0 | 0 | 6 | 3 | inf |\n", "| 2 | Availability_of_semi_elaborate | 3 | 0 | 3 | 0 | inf |\n" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.6" } }, "nbformat": 4, "nbformat_minor": 0 }